package com.hyc.algorithm.sort;

import java.util.Arrays;

/**
 * @projectName: DataStructure
 * @package: com.hyc.algorithm.sort
 * @className: mergeSort
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/4/3 18:08
 * @version: 1.0
 */
public class mergeSort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 9, 2, 6, 8, 7, 5};
        System.out.println(Arrays.toString(mergeSort(arr)));
    }

    public static int[] mergeArr(int[] arr1, int[] arr2) {
        if (arr1 == null) {
            return arr2;
        }
        if (arr2 == null) {
            return arr1;
        }
        //结果集数组
        int[] result = new int[arr1.length + arr2.length];
        //记录第一个数组的遍历索引
        int p1 = 0;
        //记录第二个数组的遍历索引
        int p2 = 0;
        //记录结果数组的遍历索引
        int pr = 0;

        //只要有一个数组没有遍历完就继续循环
        while (p1 < arr1.length || p2 < arr2.length) {
            if (p2 >= arr2.length || p1 < arr1.length && arr1[p1] <= arr2[p2]) {
                result[pr] = arr1[p1];
                p1++;
            } else {
                result[pr] = arr2[p2];
                p2++;
            }
            pr++;
        }
        return result;
    }

    public static int[] mergeSort(int[] arr, int begin, int end) {
        if (end - begin > 2) {
            //   需要向下递归
            int[] resultA = mergeSort(arr, begin, begin + (end - begin) / 2);
            int[] resultB = mergeSort(arr, begin + (end - begin) / 2, end);
            return mergeArr(resultA, resultB);
        } else if (end - begin == 1) {
            //只有一个数字的时候 直接返回
            return Arrays.copyOfRange(arr, begin, end);
        } else if (arr[begin] < arr[begin + 1]) {
            //前一个小于下一个的时候 相当于已经有序 返回
            return new int[]{arr[begin], arr[begin + 1]};
        } else {
            //之后的条件才是需要交换
            return new int[]{arr[begin + 1], arr[begin]};
        }
    }

    public static int[] mergeSort(int[] arr) {
        if (arr == null) {
            return arr;
        }
        return mergeSort(arr, 0, arr.length);
    }
}
